package com.yangli.leecode.mashib.interview;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/27 14:35
 */
public class FiftyEight {


    public static int[] function(int arr[]){
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        HashMap<Integer, Map<Integer, Integer>> map = new HashMap<>();//key表示0的比例，value的key表示1的比例，value的key表示0:1出现次数
        int res[] = new int[arr.length];
        int zero = 0;//0的数量
        int one = 0;//1的数量
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                one++;
            } else {
                zero++;
            }
            if (zero == 0 || one == 0) {
                res[i] = i + 1;//全是0或者为1时候，前缀分割就单独的个数
                continue;
            }
            int gcd = gcd(one, zero);
            int zeroGcd = zero / gcd;
            int oneGcd = one / gcd;

            //如果前面0:1比例a有n个，那当前0:1比例为a，有n+1个
            if (map.containsKey(zeroGcd) && map.get(zeroGcd).containsKey(oneGcd)) {
                Integer count = map.get(zeroGcd).get(oneGcd) + 1;
                map.get(zeroGcd).put(oneGcd, count);
                res[i] = count;
            } else {
                Map<Integer, Integer> temp = new HashMap<>();
                temp.put(oneGcd, 1);
                map.put(zeroGcd, temp);
                res[i] = 1;
            }
        }
        return res;
    }


    public static void main(String[] args){
/*        System.out.println(FiftyEight.gcd(28, 6));
        System.out.println(FiftyEight.lcm(6, 28));*/

        System.out.println(Arrays.toString(FiftyEight.function(new int[]{0, 0, 1, 1, 0, 0, 0, 0, 1})));
        System.out.println(FiftyEight.kthMax("sbajszedafwzasqwe", 6));
        System.out.println(FiftyEight.maxValue(new int[]{0, 0, 1, 1, 0, 0, 0, 1, 1}));
        System.out.println(FiftyEight.maxValue2(new int[]{0, 0, 1, 1, 0, 0, 0, 1, 1}));

    }

    public static String kthMax(String str, int k){
        if (str == null || str.length() == 0) {
            return "";
        }
        char stack[] = new char[str.length()];
        int size = 0;
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            while (size != 0 && stack[size - 1] < chars[i] && size + chars.length - i > k) {//栈顶元素小于当前字符，栈顶弹出   栈元素+剩余元素要大于k数量才进行弹出，否则不能弹出了
                size--;
            }
            stack[size++] = chars[i];

        }
        StringBuilder stringBuilder = new StringBuilder();
        int count = 1;
        while (count <= k) {
            stringBuilder.append(stack[--size]);
            count++;
        }

        return stringBuilder.reverse().toString();
    }


    public static int maxValue(int arr[]){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int zero = 0;//0的数量
        int one = 0;//1的数量
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                one++;
            } else {
                zero++;
            }
        }
        int choose = Math.max(zero, one);
        int res = choose * (choose + 1) / 2;
        int tag = choose == zero ? 1 : 0;
        if (zero == one) {
            tag = arr[arr.length - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] == tag) {
                res += arr.length - i;
            } else {
                break;
            }
        }
        return res;
    }

    public static int maxValue2(int arr[]){
        if (arr == null || arr.length == 0) {
            return 0;
        }

        return process(arr, 0, -1, 0);
    }


    public static int process(int arr[], int i, int pre, int preValue){
        if (i == arr.length) {
            return 0;
        }
        int no = process(arr, i + 1, pre, preValue);
        int value = (pre == -1 || arr[pre] != arr[i]) ? 1 : preValue + 1;
        int yes = process(arr, i + 1, i, value);
        return Math.max(0 + no, value + yes);
    }

    //最小公约数
    public static int gcd(int a, int b){
        while (a != b) {
            if (a > b) {
                return gcd(b, a - b);
            } else {
                return gcd(a, b - a);

            }
        }
        return a;
    }

    //最小公倍数
    public static int lcm(int a, int b){
        int r = gcd(a, b);
        return a * b / r;
    }
}
